package mine.personal.demo.pratice.algorithm.slidewindow;

import java.util.*;

public class Solution {
    /**
     * @description leetcode 最大连续1的个数 III
     * @param nums
     * @param k
     * @return int
     * @author 李鸿麟
     * @since 2024/9/21     */
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        int zero = 0;
        int res = 0;
        int left = 0;
        int right = 0;
        while (right < n) {
            if (nums[right++] == 0) {
                zero++;
            }

            while (zero > k) {
                if (nums[left++] == 0) {
                    zero--;
                }
            }
            res = Math.max(res, right - left);
        }
        return res;
    }

    /**
     * @description
     * 这个是老师写的
     * @param ss
     * @return int
     * @author 李鸿麟
     * @since 2024/9/17     */
    public  int lengthOfLongestSubstringByTeacher(String ss) {
        char[] s = ss.toCharArray();

        int[] hash = new int[128];
        int left = 0, right = 0, ret = 0, n = ss.length();

        while (right < n) {
            hash[s[right]]++;
            while (hash[s[right]] > 1) {
                hash[s[left++]]--;
            }
            ret = Math.max(ret, right - left + 1);
            right++;
        }

        return ret;
    }

    /**
     * @descipiton leetcode 无重复字符的最长子串
     * 这个是自己写的
     * @param s
     * @return int
     * @author 李鸿麟
     * @since 2024/9/17     */
    public  int lengthOfLongestSubstring(String s) {
        char[] charArray = s.toCharArray();
        int n = charArray.length;
        int len = 0;
        HashSet<Character> set = new HashSet<>();
        if (s.length() == 1) {
            return 1;
        }
        for (int left = 0, right = 0; right < n; right++) {
            if (!set.contains(charArray[right])) {
                set.add(charArray[right]);
            } else {
                len = Math.max(len, set.size());
                for (; left < right; left++) {
                    if (charArray[left] == charArray[right]) {
                        left++;
                        break;
                    }
                    set.remove(charArray[left]);
                }
            }
        }
        return (len < set.size() ? set.size() : len);
    }

    /**
     * @description: leetcode 长度最小的子数组
     * 这个题事实上还是双指针，但是与前面做的题不同，这个题的双指针的移动是同向的。这就意味着两个双指针之间形成了一个“滑动窗口”（而之前的题目两个指针是相向运动的）
     * 滑动窗口在这道题有几个比较重要的点
     * 1.滑动窗口正确的原因是减少了暴力枚举中很多不必要的组合，而减少的这些组合是通过数组的特定条件和单调性分析出来的
     * 2.滑动窗口类型的题目往往需要重点分析进窗口和出窗口的条件
     * 3.滑动窗口在更新窗口内的元素师需要慎重
     * @param target
     * @param nums
     * @return int
     * @author 李鸿麟
     * @since 2024/9/17     */
    public int minSubArrayLen(int target, int[] nums) {
        int len = Integer.MAX_VALUE;
        int n = nums.length, sum = 0;
        for (int left = 0, right = 0; right < n; right++) {
            sum += nums[right];
            while (sum >= target) {
                len = Math.min(len, right - left + 1);
                sum -= nums[left++];
            }
        }
        return (len == Integer.MAX_VALUE ? 0 : len);
    }

    /**
     * @description: leetcode 1658.将 x 减到 0 的最小操作数
     * @param nums
     * @param x
     * @return int
     * @author 李鸿麟
     * @since 2025/1/14     */
    public int minOperations(int[] nums, int x) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int len = -1;
        int y = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum - x < 0) {
            return -1;
        }
        for (; right < nums.length; right++) {
            y += nums[right];
            while (y > sum - x) {
                y -= nums[left++];
            }
            if (y == sum - x) {
                len = Math.max(len, right - left + 1);
            }
        }
        return len == -1 ? len : nums.length - len;
    }

    /**
     * leetcode 904. 水果成篮
     * @param fruits 果数群
     * @return int
     * @author 李鸿麟
     * @since 2025/1/16     */
    public static int totalFruit(int[] fruits) {
        // 只存水果的种类但是不存水果的个数，就无法在出窗口的时候保证窗口合法
        HashMap<Integer, Integer> buckets = new HashMap<>();
        int res = 0;
        int size = 2;
        for (int left = 0, right = 0; right < fruits.length; right++) {
            // 1.进窗口
            if (!buckets.containsKey(fruits[right])) {
                buckets.put(fruits[right], 1);
            } else {
                buckets.put(fruits[right], buckets.get(fruits[right]) + 1);
            }

            // 2.判断窗口是否合法
            while (buckets.size() > size) {
                buckets.put(fruits[left], buckets.get(fruits[left]) - 1);
                if (buckets.get(fruits[left]) == 0) {
                    buckets.remove(fruits[left]);
                }
                left++;
            }
            res = Math.max(right - left + 1, res);
        }

        return res;
    }


    public static void main(String[] args) {
        int[] test = new int[]{3,3,3,1,2,1,1,2,3,3,4};

        System.out.println(totalFruit(test));
    }
}
